package com.liy.teaching;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**

    布隆过滤器判断 不存在  准确率100%

    布隆过滤器判断 存在    准确率不是100%, 也就是说存在误差,不准确

    可以判断某样东西一定不存在
    或者
    可以判断某样东西可能存在

 总结: 误判率可以通过fpp参数进行调节
    fpp越小，需要的内存空间就越大：0.01需要900多万位数，0.03需要700多万位数。
    fpp越小，集合添加数据时，就需要更多的hash函数运算更多的hash值，去存储到对应的数组下标里。（忘了去看上面的布隆过滤存入数据的过程）
    下面的numBits，表示存一百万个int类型数字，需要的位数为7298440，700多万位。理论上存一百万个数，一个int是4字节32位，需要481000000=3200万位。如果使用HashMap去存，按HashMap50%的存储效率，需要6400万位。可以看出BloomFilter的存储空间很小，只有HashMap的1/10左右
    下面的numHashFunctions表示需要几个hash函数运算，去映射不同的下标存这些数字是否存在（0 or 1）。
 */
public class BloomFilterCase {

    /**
     * 预计要插入多少数据
     */
    private static int size = 1000000; //一百万

    /**
     * 误判率
     */
    private static double fpp = 0.000001;

    /*
        funnel：数据类型(一般是调用Funnels工具类中的)
        expectedInsertions：期望插入的值的个数
        fpp：误判率(默认值为0.03)
        strategy：哈希算法
     */
    /**
     * 布隆过滤器
     */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);


    public static void main(String[] args) {

        // 插入一百万样本数据
        for (int i = 0; i < size; i++) {  // 从 0 ~ 1000000 (不包含1000000)
            bloomFilter.put(i);
        }


        // 用另外 十万测试数据，测试误判率
        int count = 0;

        for (int i = size; i < size + 100000; i++) {  //  1000000 ~ 1100000 (不包含1100000)

            if ( bloomFilter.mightContain(i)  ) {
                count++;
                System.out.println(i + "误判了");
            }
        }

        System.out.println("总共的误判数:" + count);
    }
}
